//
// Created by HP on 2022/3/8.
//

// std
#include <stdlib.h>
#include <string.h>
#include <windows.h>

#include "fontRaster.h"

int compare_ints(const void* a, const void* b)
{
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

void scanLine(Glyph *glyphs, int size) {
    // 1. 初始化 NET
    // 1.1 确定 N
    int y_max, y_min, N;
    y_max = INT_MIN;
    y_min = INT_MAX;
    for (int i = 0; i < size; i++) {
        Vertex *vertices = glyphs[i].vertices;
        for (int j = 0; j < glyphs[i].size; j++) {
            int y = (int)(vertices[j].y);
            if (y < y_min) {
                y_min = y;
            }
            if (y > y_max) {
                y_max = y;
            }
        }
    }
    N = y_max - y_min + 1;
    Edge* *NET = (Edge* *) malloc(sizeof(Edge*) * N);
    memset(NET, 0, sizeof(Edge*) * N);
    // 1.2 根据点对确定线段表示, 并填入 NET 中
    for (int i = 0; i < size; i++) {
        initNET(glyphs[i], NET, y_min);
    }
    // 2. 初始化扫描线
    int y_scan = y_min;
    Edge* AET = malloc(sizeof(Edge));  // 初始化 AET
    AET->next = NULL;

    int   cnt = 0; // AET 中元素数量
    int xs[50];   // 实在无法想象有什么字体在一条线上有超过 50 个交点
    // 3. 绘制
    for (int i = 0; i < N; i++) {
        // 3.1 将 NET[y_scan - y_min] 中所有的元素加入 AET 中
        //     i = y_scan - y_min
        if (NET[i] != NULL) {
            Edge* edges = NET[i];
            Edge* rest = AET->next;
            // 头插法
            AET->next = edges;
            // 记数
            while (edges->next != NULL) {
                edges = edges->next;
                cnt++;
            }
            cnt++;
            // 连接到原有元素
            edges->next = rest;
        }
        // 3.2 将 AET 中的元素按 x_sta 升序排列
        // 3.3 两两匹配点对 (pi, pj), 并填充平行线 pi-pj
        // 这两步中我们实际上只是要用到 x 的值, 所以我们可以只对 x 进行排序
        // 在取出 x 的时候, 我们就可以对 线段 进行更新

        Edge *work = AET->next;
        for (int j = 0; j < cnt; j++) {
            if (work == NULL) break;
            // 取出 x 值
            xs[j] = (int)(work->x_sta);
            // 更新
            work->x_sta += work->dx;
            work = work->next;
        }
        qsort(xs, cnt, sizeof(int), compare_ints);
        // 3.3 两两匹配, 填充平行线
        int start = 0;
        if (cnt % 2 == 1) start = 1;
        while (start + 1 < cnt) {
            int x_start = xs[start];
            int x_end = xs[start + 1];
            for (int x = x_start; x <= x_end; x++) {
                drawPixel(x, y_scan);
            }
            start += 2;
        }
        // 删除边
        work = AET;
        y_scan++;
        while (work->next != NULL) {
            if (work->next->y_end == y_scan) {
                // 删除边
                Edge* need_delete = work->next;
                work->next = need_delete->next;
                free(need_delete);
                cnt--;
                continue;
            }
            work = work->next;
            if (work == NULL) break;
        }
    }
}

void initNET(Glyph glyph, Edge* *NET, int y_min) {
    Vertex *vertices = glyph.vertices;
    int size = glyph.size;
    for (int i = 0; i < size; i++) {
        double x0, x1, y0, y1, dx;
        y0 = vertices[(i - 1 + size) % size].y;
        y1 = vertices[i].y;
        double diff = y1 - y0;
        if (diff < 0) diff = -diff;
        if (diff < 1e-5) continue;
        x0 = vertices[(i - 1 + size) % size].x;
        x1 = vertices[i].x;

        dx = (x1 - x0) / (y1 - y0);

        double x_sta;
        int y_sta, y_end;
        if (y0 > y1) {
            y_sta = (int)y1;
            x_sta = (int)x1;

            y_end = (int)y0;
        } else {
            y_sta = (int)y0;
            x_sta = (int)x0;

            y_end = (int)y1;
        }
        // 创建新边
        Edge *new_edge = malloc(sizeof(Edge));
        new_edge->x_sta = x_sta;
        new_edge->y_end = y_end;
        new_edge->dx = dx;
        new_edge->next = NULL;
        // 插入 NET
        int idx = y_sta - y_min;
        if (NET[idx] != NULL) {
            Edge* rest = NET[idx]->next;
            NET[idx]->next = new_edge;
            new_edge->next = rest;
        } else {
            NET[idx] = new_edge;
        }
    }
}
